A Hybrid Adjacency and Time-Based Data Structure for Analysis of Temporal Networks
- Project Research
- 1-5 Chapters
- Abstract : Available
- Table of Content: Available
- Reference Style: APA
- Recommended for : Student Researchers
- NGN 3000
Background
Related Work I begin with background information on ways for representing temporal networks and data structures for storing (static) networks. I then discuss work related to this thesis, including the use of hybrid data structures and other types of temporal network data structures. 2.1 Static Network Representations Static networks are typically represented in one of 3 ways [41]: • Adjacency matrix : A two-dimensional matrix, Auv, stores edge information for source node u to destination node v in the uvth element of the matrix. • Adjacency list: A set of lists, one for each source node u. Each list contains a series of destination nodes v, if edge (u, v) exists. • Adjacency dictionary: A hash table keyed by source nodes u mapped to the set of destination nodes v, if edge (u, v) exists. The adjacency matrix is the traditional data structure for network representation due to, in part, its simple construction, but also its prominence in key aspects of network analysis, such as spectral graph theory. The values stored in adjacency 7 matrices are typically boolean in nature, with a value of ”1” representing an edge is present between two nodes, and a value of ”0” otherwise. However, adjacency matrices can be modified to hold additional information by storing numeric values instead, e.g. edge weights. Since an adjacency matrix stores a value for both present and missing edges, it has a memory complexity of O(n 2 ), where n is the number of nodes, and is therefore only appropriate for smaller networks. The adjacency list representation aims to improve upon this memory complexity by removing the need to store missing edge information. By storing edges as a set of list, adjacency lists improve the memory complexity to O(k), where k is the number of edges. However, this approach suffers from increased time complexity during common operations such as finding if an edge exists between nodes u and v due to the unsorted nature of its lists. The adjacency dictionary representation is a variant on the standard adjacency list, by storing the edges in a hashed set rather than a list. Edges presence in an adjacency dictionary can be determined in O(1) time, matching the adjacency matrix, while retaining the O(k) space complexity of the adjacency list. By using a hash table instead of a hashed set, additional edge information can be stored inside the adjacency dictionary as well.
Related Project Materials
AN EVALUATION OF GREEN HUMAN RESOURCES AND EMPLOYEES' BEHAVIOR IN HOTEL INDUSTRY
Background Of The Study
Green management has grown in popularity among industry and academia as a way t...
INFORMATION RETRIEVAL METHODS (A CASE STUDY OF ONITSHA DIVISIONAL LIBRARY)
ABSTRACT
This study aims at finding the information retrieval system is basically a system that stores records in a file...
THE RELEVANCE OF MARKETING INFORMATION SYSTEM IN THE ACHIEVEMENT OF ORGANIZATIONAL OBJECTIVE
EXCERPT FROM THE STUDY
Marketing information is often obtained from outside the organization management perceives the op...
DETERMINANTS AND ADOPTION OF POINT OF SALES OF SELECTED BUSINESS ORGANISATIONS
ABSTRACT
Nigerian payment systems are cash-driven because cash is the main mode of payments for several transactions. However, the Point...
MANAGEMENT OF FARMERS MULTI-PURPOSE CO-OPERATIVE SOCIETIES
Background of the study
The cooperative movement in a programme designed to bring independent persons together for the b...
ASSESSMENT OF THE IMPACT OF ENVIRONMENTAL FACTORS ON EFFECTIVE TEACHING AND LEARNING OF PHYSICAL EDUCATION AND SPORTS AND SPORTS
ABSTRACT
This study explored the impact of environmental factors on the effective teaching and learning...
AN ASSESSMENT OF THE EFFECTIVENESS OF NEWSPAPER COVERAGE OF KIDNAPPING IN NIGERIA COMPARATIVE STUDY OF THE PUNCH AND DAILY VANGUARD
ABSTRACT
The issue of terrorism has attracted global attention. In Nigeria in particular, the terrorist...
AN EVALUATION OF THE NATURE AND IMPACT OF PLANNING ON ORGANISATIONAL PERFORMANCE
ABSTRACT
The broad objective of this study is to examine an evaluation of the nature and impact of plan...
TEACHER’S MOTIVATION AND PRODUCTIVITY IN SECONDARY SCHOOLS
EXCERPT FROM THE STUDY
Productivity is a concept often misinterpreted with efficiency by many people. However, both conc...
COMBINATORIAL PROPERTIES OF THE ALTERNATING & DIHEDRAL GROUPS AND HOMOMORPHIC IMAGES OF FIBONACCI GROUPS
Abstract
Let Xn = { } 1,2,…,n be a finite n -element set and let Sn An and Dn , be the Symmetric, Alternating and Dihedral groups...
